{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #统计目标成绩的出现次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计目标成绩的出现次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>某班级考试成绩按非严格递增顺序记录于整数数组 <code>scores</code>，请返回目标成绩 <code>target</code> 的出现次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> scores = [2, 2, 3, 4, 4, 4, 5, 6, 6, 8], target = 4\n",
    "<strong>输出:</strong> 3</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> scores = [1, 2, 3, 5, 7, 9], target = 6\n",
    "<strong>输出:</strong> 0</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= scores.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= scores[i]&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>scores</code>&nbsp;是一个非递减数组</li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= target&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与主站 34 题相同（仅返回值不同）：<a href=\"https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/\">https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/</a></p>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof](https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof](https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,3,4,4,4,5,6,6,8]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        counter = Counter(scores)\n",
    "        return counter[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        # 采用二分搜索法，找到第一个之后，沿着左右找就行\n",
    "        # 注意，采用左闭右开区间\n",
    "        if not scores:\n",
    "            return 0\n",
    "        left = 0\n",
    "        right = len(scores)\n",
    "\n",
    "        while left < right:\n",
    "            mid = int((left + right) / 2) # 取中间偏右的那个\n",
    "            if scores[mid] == target:\n",
    "                tmp_left = mid\n",
    "                tmp_right = mid\n",
    "                while tmp_left>=0 and scores[tmp_left] == target:\n",
    "                    tmp_left -= 1\n",
    "                tmp_left += 1\n",
    "                while tmp_right<len(scores) and scores[tmp_right] == target:\n",
    "                    tmp_right += 1\n",
    "                tmp_right -= 1\n",
    "                return tmp_right - tmp_left + 1\n",
    "            elif scores[mid] < target:\n",
    "                left = mid + 1\n",
    "            elif scores[mid] > target:\n",
    "                right = mid # 右边是开区间\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def upper_bound(a, x):\n",
    "            l, r = 0, len(a)\n",
    "            while l < r:\n",
    "                # fst > x\n",
    "                m = l + (r-l)//2\n",
    "                if a[m] <= x:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "            return l\n",
    "        \n",
    "        def lower_bound(a, x):\n",
    "            l, r = 0, len(a)\n",
    "            while l < r:\n",
    "                # fst >= x\n",
    "                m = l + (r-l)//2\n",
    "                if a[m] < x:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "            return l\n",
    "        \n",
    "        l, r = lower_bound(scores, target), upper_bound(scores, target)\n",
    "        # print(l, r)\n",
    "        # if l == len(scores) or scores[l] != target:\n",
    "        #     return 0\n",
    "        # else:\n",
    "        #     return r-l\n",
    "        return r-l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        # 搜索右边界 right\n",
    "        i, j = 0, len(scores) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if scores[m] <= target: i = m + 1\n",
    "            else: j = m - 1\n",
    "        right = i\n",
    "        # 若数组中无 target ，则提前返回\n",
    "        if j >= 0 and scores[j] != target: return 0\n",
    "        # 搜索左边界 left\n",
    "        i = 0\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if scores[m] < target: i = m + 1\n",
    "            else: j = m - 1\n",
    "        left = j\n",
    "        return right - left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        count = Counter(scores)\n",
    "        return count[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return scores.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        count =0\n",
    "        for i in scores:\n",
    "            if i == target:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        left = bisect.bisect_left(scores, target)\n",
    "        right= bisect.bisect_right(scores, target)\n",
    "        return right-left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        A = {}\n",
    "        for i in scores:\n",
    "            if i in A.keys():\n",
    "                A[i]+=1\n",
    "            else:\n",
    "                A[i]=1\n",
    "        if target in A.keys():\n",
    "            return A[target]\n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def helper(tar):\n",
    "            i, j = 0, len(scores) - 1\n",
    "            while i <= j:\n",
    "                m = i + (j-i) // 2\n",
    "                if scores[m] <= tar: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return j\n",
    "        return helper(target) - helper(target - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        c = Counter(scores)\n",
    "        return c.get(target, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        count = 0\n",
    "        for i in scores:\n",
    "            if i == target:\n",
    "                count +=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        \n",
    "    \n",
    "        return scores.count(target)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if scores == []: return 0\n",
    "        def binary_search(nums:List[int], target):\n",
    "            l, r = 0, len(nums)\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if nums[mid] < target:\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid \n",
    "            return l\n",
    "        return binary_search(scores, target + 1) - binary_search(scores, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return collections.Counter(scores)[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        left = 0\n",
    "        right = len(scores)-1\n",
    "        left_bound = 0\n",
    "        right_bound = right\n",
    "        while left <= right:\n",
    "            if scores[left] == target:\n",
    "                left_bound = left\n",
    "                break\n",
    "            mid = int(left + (right - left)/2)\n",
    "            if scores[mid] < target:\n",
    "                if mid+1 <len(scores) and scores[mid + 1] == target:\n",
    "                    left_bound = mid + 1\n",
    "                    break\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            else: \n",
    "                right = mid - 1\n",
    "        if left > right:\n",
    "            return 0\n",
    "\n",
    "        left = left_bound\n",
    "        right = len(scores) - 1\n",
    "        while left <= right:\n",
    "            mid = int(left + (right - left)/2)\n",
    "            if scores[mid] > target:\n",
    "                if scores[mid - 1] == target:\n",
    "                    right_bound = mid -1\n",
    "                    break\n",
    "                else:\n",
    "                    right = mid-1 \n",
    "            else: #=target\n",
    "                left = mid + 1\n",
    "\n",
    "        return right_bound-left_bound+1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return Counter(scores)[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        count, fast = 0, 0\n",
    "        i = 0\n",
    "        while fast < len(scores):\n",
    "            if scores[fast] == target:\n",
    "                count += 1\n",
    "            fast += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        dic={}\n",
    "        val=0\n",
    "        for i in scores:\n",
    "            if i in dic:\n",
    "                dic[i]+=1\n",
    "            else:\n",
    "                dic[i]=1\n",
    "        if target in dic:\n",
    "                val=dic[target]\n",
    "        return val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, nums: List[int], target: int) -> int:\n",
    "        l = bisect_left(nums, target)\n",
    "        r = bisect_right(nums, target)\n",
    "        return r - l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if not scores:\n",
    "            return 0\n",
    "        i, j = 0, len(scores) - 1\n",
    "        while i < j:\n",
    "            mid = (i + j + 1) // 2\n",
    "            if scores[mid] < target:\n",
    "                i = mid\n",
    "            else:\n",
    "                j = mid - 1\n",
    "        start = i\n",
    "        i, j = 0, len(scores) - 1\n",
    "        while i < j:\n",
    "            mid = (i + j) // 2\n",
    "            if scores[mid] > target:\n",
    "                j = mid\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        \n",
    "        end = i\n",
    "        print(start, end)\n",
    "        if start == end:\n",
    "            return 1 if scores[start] == target else 0\n",
    "        if scores[start] == target:\n",
    "            start -= 1\n",
    "        if scores[end] == target:\n",
    "            end += 1\n",
    "        return end - start - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        i,j=0,len(scores)-1\n",
    "        while i<=j:\n",
    "            m=(i+j)//2\n",
    "            if scores[m]<=target:i=m+1\n",
    "            else:j=m-1\n",
    "        right=i\n",
    "        if j>=0 and scores[j]!=target:return 0\n",
    "        i=0\n",
    "        while i<=j:\n",
    "            m=(i+j)//2\n",
    "            if scores[m]<target:i=m+1\n",
    "            else:j=m-1\n",
    "        left=j\n",
    "        return right-left-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        count=1\n",
    "        result=self.find(scores,target)\n",
    "        if result==-1:\n",
    "            return 0\n",
    "        for i in range(result-1,-1,-1):\n",
    "            if scores[i]!=target:\n",
    "                break\n",
    "            count+=1\n",
    "        for i in range(result+1,len(scores)):\n",
    "            if scores[i]!=target:\n",
    "                break\n",
    "            count+=1\n",
    "        return count\n",
    "\n",
    "    def find(self, scores: List[int], target: int):\n",
    "        i,j=0,len(scores)-1\n",
    "        while i<=j:\n",
    "            m=(i+j)//2\n",
    "            if scores[m]<target:\n",
    "                i=m+1\n",
    "            elif scores[m]>target:\n",
    "                j=m-1\n",
    "            else:\n",
    "                return m\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def helper(tar):\n",
    "            i, j = 0, len(scores) - 1\n",
    "            while i <= j:\n",
    "                m = (i + j) // 2\n",
    "                if scores[m] <= tar: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return i\n",
    "        return helper(target)-helper(target-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        hmap = {}\n",
    "        for i in scores:\n",
    "            if i in hmap:\n",
    "                hmap[i] += 1\n",
    "            else:\n",
    "                hmap[i] = 1\n",
    "        return hmap.get(target, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return Counter(scores)[target]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def helper(tar):\n",
    "            i, j = 0, len(scores) - 1\n",
    "            while i <= j:\n",
    "                m = (i + j) // 2\n",
    "                if scores[m] <= tar: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return i\n",
    "        return helper(target) - helper(target - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores, target):\n",
    "        ans = 0\n",
    "        n = len(scores)\n",
    "        left, right = 0, n - 1\n",
    "        \n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if scores[mid] == target:\n",
    "                i, j = mid, mid\n",
    "                while i >= 0 and scores[i] == target:\n",
    "                    i = i - 1\n",
    "                while j < n and scores[j] == target:\n",
    "                    j = j + 1\n",
    "                ans = j - i - 1\n",
    "                break\n",
    "            elif scores[mid] < target:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return scores.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if not scores:return 0\n",
    "        l = 0\n",
    "        r = len(scores) - 1\n",
    "        length = 0\n",
    "        while scores[l]!=target:\n",
    "            if l<r:l+=1\n",
    "            else:return 0\n",
    "        while scores[r]!=target:\n",
    "            if l<r:r-=1\n",
    "        length = r-l+1\n",
    "        return length"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(scores)):\n",
    "            if scores[i] == target:\n",
    "                res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        i,j = 0, len(scores)-1\n",
    "        mid = -1\n",
    "        while i<=j:\n",
    "            mid = (i+j)//2\n",
    "            if scores[mid] == target:\n",
    "                break\n",
    "            elif scores[mid] > target:\n",
    "                j = mid-1\n",
    "            else:\n",
    "                i = mid+1\n",
    "        \n",
    "        result = 0\n",
    "        i,j = mid, mid+1\n",
    "        while j<len(scores) and scores[j] == target:\n",
    "            j+=1\n",
    "            result+=1\n",
    "        while i>=0 and scores[i] == target:\n",
    "            i-=1\n",
    "            result+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def helper(tar):\n",
    "            i, j = 0, len(scores) - 1\n",
    "            while i <= j:\n",
    "                m = (i + j) // 2\n",
    "                if scores[m] <= tar: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return i\n",
    "        return helper(target) - helper(target - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if len(scores) == 0:\n",
    "            return 0\n",
    "\n",
    "        # 二分法找出最后一个比target小的位置p1\n",
    "        # 二分法找出第一个比target大的位置p2\n",
    "        # res = p2 - p1 - 1\n",
    "        i, j = 0, len(scores) - 1\n",
    "        while i <= j:\n",
    "            mid = int((i + j) / 2)\n",
    "            if scores[mid] >= target:\n",
    "                j = mid - 1\n",
    "            else:\n",
    "                i = mid + 1\n",
    "        p1 = i - 1\n",
    "\n",
    "        i, j = p1 + 1, len(scores) - 1\n",
    "        while i <= j:\n",
    "            mid = int((i + j) / 2)\n",
    "            if scores[mid] == target:\n",
    "                i = mid + 1\n",
    "            else:\n",
    "                j = mid - 1\n",
    "        p2 = i\n",
    "\n",
    "        return max(0, p2 - p1 - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return scores.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        # 数组双指针：二分查找\n",
    "        def findindex(nums, tar):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] >= tar:\n",
    "                    right = mid - 1\n",
    "                elif nums[mid] < tar:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    return mid\n",
    "            return right + 1\n",
    "\n",
    "        lindex = findindex(scores, target)\n",
    "        rindex = findindex(scores, target + 1) - 1\n",
    "        return rindex - lindex + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        result = 0\n",
    "        if not scores: return result\n",
    "        for i in scores:\n",
    "            if i < target: continue\n",
    "            elif i == target: result += 1\n",
    "            else: break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return scores.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        count=0\n",
    "        for i in scores:\n",
    "            if i == target:\n",
    "                count+=1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        flag = 0\n",
    "        for i in range(len(scores)):\n",
    "            if scores[i] == target:\n",
    "                flag += 1\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        i, j = 0, len(scores) - 1\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if scores[m] <= target:\n",
    "                i = m + 1\n",
    "            else:\n",
    "                j = m - 1\n",
    "        right = i\n",
    "        if j >= 0 and scores[j] != target:\n",
    "            return 0\n",
    "        i = 0\n",
    "        while i <= j:\n",
    "            m = (i + j) // 2\n",
    "            if scores[m] >= target:\n",
    "                j = m - 1\n",
    "            else:\n",
    "                i = m + 1\n",
    "        left = j\n",
    "        return right - left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        i=0\n",
    "        j=len(scores)-1\n",
    "        while i<=j:\n",
    "            if (scores[i]<target) :\n",
    "                i+=1\n",
    "            elif scores[j]>target:\n",
    "                j-=1\n",
    "            else:\n",
    "                break\n",
    "        if j>=i:\n",
    "            return j-i+1    \n",
    "        else:\n",
    "            return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def first(nums,l,r,target):\n",
    "            while l<r:\n",
    "                mid=l+(r-l)//2\n",
    "                if nums[mid]>target:\n",
    "                    r=mid-1\n",
    "                elif nums[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    r=mid\n",
    "            return l if nums[l]==target else -1\n",
    "        def last(nums,l,r,target):\n",
    "            while l<r:\n",
    "                mid=(r-l+1)//2 +l\n",
    "                if nums[mid]>target:\n",
    "                    r=mid-1\n",
    "                elif nums[mid]<target:\n",
    "                    l=mid+1\n",
    "                else:\n",
    "                    l=mid\n",
    "            return l if nums[l]==target else -1\n",
    "        if len(scores)==0:\n",
    "            return 0\n",
    "        i=first(scores,0,len(scores)-1,target)\n",
    "        if i==-1:\n",
    "            return 0\n",
    "        j=last(scores,0,len(scores)-1,target)\n",
    "        return j-i+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        # 二分搜索，查找左和右\n",
    "        l=0\n",
    "        r=len(scores)-1\n",
    "        left_index=-1\n",
    "        while l<=r:\n",
    "            if l==r:\n",
    "                if scores[l]==target:\n",
    "                    left_index=l\n",
    "                break\n",
    "            mid=(l+r)//2\n",
    "            if scores[mid]>target:\n",
    "                r=mid-1\n",
    "            elif scores[mid]<target:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                r=mid\n",
    "                left_index=mid\n",
    "        if left_index==-1:\n",
    "            return 0\n",
    "        right_index=-1\n",
    "        l=0\n",
    "        r=len(scores)-1\n",
    "        while l<=r:\n",
    "            if l==r:\n",
    "                if scores[r]==target:\n",
    "                    right_index=r\n",
    "                break\n",
    "            mid=(l+r)//2\n",
    "            if scores[mid]>target:\n",
    "                r=mid-1\n",
    "            elif scores[mid]<target:\n",
    "                l=mid+1\n",
    "            else:\n",
    "                l=mid+1\n",
    "                right_index=mid\n",
    "        return right_index-left_index+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if not scores: return 0\n",
    "        def bin_search(l, r, tar):\n",
    "            if l > r: return\n",
    "            while l <= r:\n",
    "                mid = (l + r) //2\n",
    "                if scores[mid] > tar:\n",
    "                    r -= 1\n",
    "                else:\n",
    "                    l += 1\n",
    "            return r\n",
    "\n",
    "        return bin_search(0, len(scores)-1, target) - bin_search(0, len(scores)-1, target-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        hx = {}\n",
    "        for i in scores:\n",
    "            hx[i] = hx.get(i, 1) + (i in hx)\n",
    "        return hx.get(target,0)\n",
    "        # l, r = 0, len(scores)-1\n",
    "        # while l<r:\n",
    "        #     mid = (l+r)//2\n",
    "        #     if scores(mid) == target:\n",
    "        #         return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def binary_search(scores, left, right, target):\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if scores[mid] == target:\n",
    "                    return mid\n",
    "                elif scores[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return None\n",
    "        \n",
    "        ind = binary_search(scores, 0, len(scores)-1, target)\n",
    "        if ind == None:\n",
    "            return 0\n",
    "        ind_ = ind\n",
    "        count = 0\n",
    "        while 0<=ind_<len(scores) and scores[ind_] == target:\n",
    "            count += 1\n",
    "            ind_ -= 1\n",
    "        ind += 1\n",
    "        while 0<=ind<len(scores) and scores[ind] == target:\n",
    "            count += 1\n",
    "            ind += 1\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        l ,r = 0, len(scores) - 1\n",
    "\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if scores[mid] <= target:\n",
    "                l = mid + 1\n",
    "            elif scores[mid] > target:\n",
    "                r = mid - 1\n",
    "        right = l\n",
    "        if r >= 0 and scores[r] != target: return 0\n",
    "        l = 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if scores[mid] < target:\n",
    "                l = mid + 1\n",
    "            elif scores[mid] >= target:\n",
    "                r = mid - 1\n",
    "        left = r \n",
    "        return right - left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        count = 0\n",
    "        for i in scores:\n",
    "            if target == i:\n",
    "                count +=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        flag = 0\n",
    "        for i in range(len(scores)):\n",
    "            if scores[i] == target:\n",
    "                flag += 1\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        # cnt = Counter(scores)\n",
    "        # return cnt.get(target, 0)\n",
    "        if len(scores) == 0:\n",
    "            return 0\n",
    "        if len(scores) == 1:\n",
    "            return int(scores[0] == target)\n",
    "        i,j = 0,len(scores)-1\n",
    "        while i <= j:\n",
    "            m = i+(j-i)//2\n",
    "            if scores[m] > target:\n",
    "                j = m-1\n",
    "            else:\n",
    "                i = m+1\n",
    "        if scores[j] != target and (i == len(scores) or j == -1):\n",
    "            return 0\n",
    "        right = j\n",
    "        i = 0\n",
    "        while i <= j:\n",
    "            m = i+(j-i)//2\n",
    "            if scores[m] >= target:\n",
    "                j = m-1\n",
    "            else:\n",
    "                i = m+1\n",
    "        left = j\n",
    "        return right - left\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if target not in scores:\n",
    "            return 0\n",
    "        else:\n",
    "            return scores.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        num=0\n",
    "        for i in range(len(scores)):\n",
    "            if scores[i]==target:\n",
    "                num+=1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return scores.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        return scores.count(target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        def helper(tar):\n",
    "            i, j = 0, len(scores) - 1\n",
    "            while i <= j:\n",
    "                m = (i + j) // 2\n",
    "                if scores[m] <= tar: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return i\n",
    "        return helper(target) - helper(target - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if not scores: return 0\n",
    "        def right_bdy(target):\n",
    "            i, j = 0, len(scores) - 1\n",
    "            while i <= j:\n",
    "                m = (i + j) // 2\n",
    "                if scores[m] <= target: i = m + 1\n",
    "                else: j = m - 1\n",
    "            return i\n",
    "        return right_bdy(target) - right_bdy(target - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 这个方法可行，但是超出了事件限制，所以还是要用查找左边界和右边界的方法\n",
    "# class Solution:\n",
    "#     def countTarget(self, scores: List[int], target: int) -> int:\n",
    "#         left, right = 0, len(scores) - 1\n",
    "#         count = 0\n",
    "#         while left <= right:\n",
    "#             mid = left + (right - left) // 2\n",
    "#             if scores[mid] == target:\n",
    "#                 count += 1\n",
    "#             elif scores[mid] > target:\n",
    "#                 right = mid - 1\n",
    "#             elif scores[mid] < target:\n",
    "#                 left = mid + 1\n",
    "#         return count\n",
    "\n",
    "# https://labuladong.gitee.io/algo/di-ling-zh-bfe1b/wo-xie-le--3c789/\n",
    "class Solution:\n",
    "    def countTarget(self, scores: List[int], target: int) -> int:\n",
    "        if self.right_bound(scores, target) == -1 or self.left_bound(scores, target) == -1:\n",
    "            count = 0\n",
    "        else:\n",
    "            count = self.right_bound(scores, target) - self.left_bound(scores, target) + 1\n",
    "\n",
    "        return count\n",
    "    \n",
    "    def left_bound(self, scores, target):\n",
    "        left, right = 0, len(scores) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if scores[mid] == target:\n",
    "                right = mid - 1\n",
    "            elif scores[mid] > target:\n",
    "                right = mid - 1\n",
    "            elif scores[mid] < target:\n",
    "                left = mid + 1\n",
    "        \n",
    "        if left < 0 or left >= len(scores):\n",
    "            return -1\n",
    "        \n",
    "        return left if scores[left] == target else -1\n",
    "\n",
    "    def right_bound(self, scores, target):\n",
    "        left, right = 0, len(scores) - 1\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if scores[mid] == target:\n",
    "                left = mid + 1\n",
    "            elif scores[mid] > target:\n",
    "                right = mid - 1\n",
    "            elif scores[mid] < target:\n",
    "                left = mid + 1\n",
    "        \n",
    "        if right < 0 or right >= len(scores):\n",
    "            return -1\n",
    "        \n",
    "        return right if scores[right] == target else -1\n",
    "\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
